This invention pertains to hardware-implemented logic systems, particularly as implemented in a neural network.
A neural network is a set of computational units whose interconnections are analogous to biological neurons. In general, any model or circuit which resembles in some way the interconnections of biological neurons can be called a neural network. Each computational unit comprises a neuron, one or more inputs, and one or more outputs. An input for one neuron may be connected to an output of another neuron. In some cases, a neuron may receive direct feedback by connecting one of its inputs to one of its own outputs. Classical neural networks are those which learn facts or patterns, and which show associative recall of the stored patterns.
Even though humans are good at logic, and though some neural networks have been modeled after human neural systems, there has been little research in the design of neural networks to solve logic problems. There are limits on the size of a logic problem which the human brain can solve in a given time. An attractive characteristic of neural networks is their scalability. There is in theory no limit to the complexity of a neural network.
Consider a logic system containing a finite number of facts. A fact can have one of two truth values-"true" or "false." Let the truth value of each fact be dependent on a finite number of rules. Each rule may depend upon the truth values of some or all of the facts. The truth value for a fact is said to be "justified" if at least one rule associated with that fact is satisfied. If the truth values of all facts are justified, then the set of all truth values is said to be consistent.
A truth maintenance system (TMS) is a particular type of logic system which solves for a consistent set of truth values from a current set of facts stored in a knowledge base. The knowledge base contains rules for determining truth values of the facts. A rule in a TMS is a set of truth values which necessarily imply that a particular fact is true. See, e.g., Jon Doyle, "A Truth Maintenance System," Artificial Intelligence, Vol 12, pp 231-272 (1979), which is incorporated by reference.
Prior TMS systems, such as described by Doyle, supra, have used a recursive labelling algorithm to reach at a correct combination of the truth values corresponding to the facts stored in the system. In practice the number of facts that can be stored in a TMS system is very large. For a set of N formulas, there are 2.sup.N possible combinations of true/false values, of which generally only a few combinations will be solutions. Given a set of formulas (or facts), the labelling algorithm fits true/false values to each formula to find solutions.
Existing software implementations of TMS systems are relatively slow, because of the large number of total possible true/false combinations, and the generally small number of such combinations which are solutions. To the knowledge of the inventors, there have been no previous logic systems implemented in neural network hardware.
Venkatasubramanian, "Inexact Reasoning in Expert Systems: A Stochastic Parallel Network Approach," IEEE Computer Society Conference on AI Applications, pp. 13-15 (1985) discusses implementing an expert system for inexact reasoning in a neural network, in which neurons are assigned to facts, constraining relationships between facts are stored as randomly assigned, symmetric interconnections of varying strength between the neurons, and updates of the neurons' states are asynchronous. However, no means for implementing this system in hardware is described. The process allows jumps from a state to lower "energy" states, where the "energy" is determined by the degree of concordance of the neurons' states and the weights of the interconnections between them. Local "energy" minima are thus reached. To attempt to avoid being stuck in local minima, occasional jumps to higher "energy" states are permitted, resulting in a Boltzmann-like distribution of states. The effective "temperature" is reduced in a "simulated annealing" algorithm, and the process is repeated several times to attempt to improve reliability. This system attempts to maximize the concordance among the various units in an inexact reasoning process, not to find precisely valid states in an exact reasoning process.
Kosko, "Adaptive Inference In Fuzzy Knowledge Networks," IEEE First International Conference on Neural Networks pp. II-261 to 268 (June 1987) describes a synchronous implementation of an expert system in a neural network, in which neurons are assigned to facts, and constraining relationships between the facts are represented by the weights of interconnections between the neurons. However, no means for implementing this system in hardware is described. There is feedback with inferencing, and the system reaches a limit cycle when an inferred solution is reached.
The classic Hopfield neural network model arrives at solutions or patterns stored in the network in terms of continuously variable interconnection weights. Known solutions are used to "teach" a Hopfield network these interconnection weights. Once the interconnection weights are determined, the network will converge to the stored pattern closest to a given arbitrary input pattern. This type of system is known as associative memory. Hopfield et al., "Computing With Neural Circuits: A Model," Science, vol. 233, pp. 625-32 (1986).